§2.1 Field of the Invention
The present invention concerns switches used in communications networks. More specifically, the present invention concerns scheduling the sending of packets through the switching fabric of such a switch.
§2.2 Background Information
The fast growth of traffic over the Internet and within data centers has led to an increasing demand for high-speed switching systems. Emerging websites and applications such as video streaming, live broadcasting and peer-to-peer communications, demand ever increasing bandwidth. In May 2010, Youtube announced that its daily video views had exceeded two billion. Cisco, incorporated herein by reference.) forecasts that by 2013, IP traffic may increase fivefold compared to 2011. (See, e.g., the article “Cisco visual networking index: Forecast and methodology, 2008 to 2013,” http://www.cisco.com/en/US/solutions/collateral/ns341/ns525/ns537/ns705/ns827/whitep aper c11-481360.pdf (2009) Also, for fast storage-access such as such as a data center, thousands of servers may have to exchange bulk data at a very high speed. Switching vendors like Cisco, Hewlett Packard and Arista plan to ship switches that can support 40/100 Gbps by 2012. Under this fast growing traffic demand, electronic technologies may not be able to support the demands of packet switches in the near future. Power consumption may also be a major problem for electronic switches, especially in data centers. Also, almost the same amount of power may be needed to cool the devices as to operate them.
Photonic technologies can provide very high bandwidth and reduce the power consumption. Unfortunately, however, an all-optical switch is still not feasible because it is difficult to buffer packets in the optical domain. Optical fiber-based buffers can have very low power dissipation, but they are very bulky. Therefore, future switching systems may have a hybrid architecture (See, e.g., the article R. S. Tucker, “The Role of Optics and Electronics in High-Capacity Routers,” Journal of Lightwave Technology, 24(12), (December 2006), incorporated herein by reference.), which exploits both electronic and optical technologies: packet buffering and processing may be done in the electronic domain, while packet switching from inputs to outputs may be implemented by an optical switching fabric. In such a hybrid architecture, arriving packets are converted to optical signals before being transmitted, and after traversing the optical fabric, are converted back to electrical signals in the electronic domain at egress linecards.
For input-queued (IQ) switches, there has been substantial research work on scheduling. (See, e.g., the articles, Y. Li, S. Panwar, and H. J. Chao, “On the Performance of a Dual Round-Robin Switch,” Proc. of IEEE INFOCOM (April 2001); J. G. Dai and B. Prabhakar, “The Throughput of Data Switches with and without Speedup,” Proc. of IEEE INFOCOM (Tel Aviv, Israel, March 2000); N. McKeown, A. Mekkittikul, V. Anantharam, and J. Walrand, “Achieving 100% Throughput in an Input-Queued Switch,” IEEE Transactions on Communications, Vol. 47, pp. 1260-1267 (August 1999); N. Mckeown, “The iSLIP Scheduling Algorithm for Input-Queued Switches,” IEEE/ACM Transactions on Networking, Vol. 7, pp. 188-201 (April 1999); and L. Tassiulas and A. Ephremides, “Stability Properties of Constrained Queuing Systems and Scheduling Policies for Maximum Throughput in Multihop Radio Networks,” IEEE Transactions on Automatic Control, 37(12), pp. 1936-1949 (December 1992), all incorporated herein by reference.) Unfortunately, these algorithms for IQ switches either do not guarantee 100% throughput, or are not suitable for distributed implementation.
Fasnet is a distributed scheduling algorithm proposed for an optical switch. (See, e.g., A. Bianco, E. Carta, D. Cuda, J. M. Finochietto, and F. Neri, “A Distributed Scheduling Algorithm for an Optical Switching Fabric,” Proc. of IEEE ICC, Beijing, China (May 2008), incorporated herein by reference.) Fasnet users used dual counter-rotating folded WDM fiber rings to connect inputs and outputs. Although, the Fasnet algorithm is distributed and simple, but it cannot achieve 100% throughput even for uniform traffic.
In view of the foregoing, it would be useful to improve scheduling in switches, such as in optical switches. It would be useful to support distributed scheduling.